The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Interactive computer graphics is the subclass of computer graphics in which a user dynamically controls the picture's content, format, size or color on a display surface by means of an interaction device such as a keyboard, lever or joystick. See Fundamentals of Interactive Computer Graphics, by J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc., in the computer's memory) is the usual domain of interactive computer graphics.
The two primary classes of interactive computer graphics systems are random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. As explained below, the data is stored in a "frame buffer."
In the random-scan system the component points of each successive output primitive are stored sequentially in memory and plotted in the same order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan system the frame buffer memory is arranged as a 2-dimensional array of data. The value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. The location of each display element is typically specified by a unique (X,Y) coordinate. Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel," short for "picture element." Hereinafter, to avoid confusion, the term "display pixel" will be used to indicate picture elements of a display device, and "storage pixel" to indicate memory locations corresponding to the display pixels. FIG. 1 is a simplified block diagram of a raster-scan graphics system 10, which includes an image creation system 12, an image storage system 14 (including a frame buffer), an image display system 16, a raster-scan display 18 and an interaction device 20. The image creation system 12 converts output primitives into the data stored in the frame buffer of the image storage system 14.
The use of color and gray scale has become an important part of modern computer graphics. The proper use of color is extremely complex because the color of an object depends not only on the object itself, but also on the light source illuminating the object and on the human visual system. Moreover, some objects only reflect light while other objects also transmit light. An observer of achromatic light does not experience any of the color sensations associated with red, blue, yellow, etc. Achromatic light is what is seen on a black and white television. The only attribute of achromatic light is its intensity. Intensity is typically represented with a scaler, e.g., 0 for black, 1 for white and 0.5 for medium gray. A black and white television can produce many different levels of gray at a single pixel position. Line printers, pen plotters and electrostatic plotters produce only two levels, the white of the paper and the black of the ink or toner deposited on the paper. A concern in computer graphics is how many intensity levels are "enough" to adequately represent an image; e.g., how many intensity levels are needed to reproduce a continuous-tone black and white photo in such a way that the reproduction appears to be continuous.
Many displays and hard-copy devices produce just two intensity levels (i.e., are "bilevel"), and even two or three bits-per-pixel raster displays produce fewer intensity levels than are often desired; however the range of available intensities is expanded through the spatial integration our eyes perform on the image. If a very small area, e.g. a 0.02.times.0.02 inch square, is viewed from a normal viewing distance, the eye will integrate fine detail within the small area and record only the overall intensity of the area. This phenomenon is used in printing black and white photos in newspapers, magazines and books, in a technique called "half toning," whereby each small resolution unit is imprinted with a circle of black ink whose area is proportional to the blackness of the area of the original photo. See Fundamentals of Interactive Computer Graphics, referenced above, pages 597-601.
Graphics output devices can approximate the variable-area dots of half tone reproduction. E.g., a 2.times.2 pixel area of a bilevel display can be used to produce five different intensity levels at the expense of cutting the spatial resolution in half along each axis. The patterns shown in FIG. 2A can be used in the 2.times.2 areas. The patterns fill each 2.times.2 area with a number of dots proportional to the desired intensity. In FIG. 2A the numerals inside the boxes represent the intensity I for the respective areas. In general, an N.times.N group of bilevel pixels can provide N.sup.2 +1 intensity levels. Spatial resolution, which is decreased, is in effect traded for intensity resolution, which is increased. The use of a 3.times.3 pattern reduces spatial resolution by a factor of 1/3 on each axis, but provides ten intensity levels. Of course even larger patterns can be used, but the spatial versus intensity resolution trade-off is limited by the human eye's visual acuity (about one minute of arc in normal lighting).
The N.times.N pixel patterns used to approximate the half tones must be designed so that they are not conspicuous in an area of identical intensity values. For example, if the pattern shown in FIG. 2B were used, horizontal lines would be visible in any large area of the image that has intensity I equal to 3. Another consideration in choosing patterns is that they form a "growth sequence," in which a pixel that is intensified for intensity level J is intensified for all levels K greater than J. This minimizes the differences in the patterns for successive intensity levels, thereby minimizing the contouring effects.
Half tone approximation is not limited to bilevel displays. If a display has two bits per pixel, and thus four intensity levels, the half tone technique may be used to further increase the number of intensity levels. If a 2.times.2 pattern is used, a total of four pixels, each of which can take on three intensity values besides black, is available, allowing the display of 4.times.3+1=13 intensity levels. One possible set of growth sequence patterns for this case is shown in FIG. 2C. The respective intensities of the individual pixels sum to the intensity level I shown below each pattern.
The above techniques are appropriate if the resolution of the image to be displayed is lower than the resolution of the display device, allowing the use of multiple display pixels for one image pixel. If the image resolution and device resolution are the same, the "ordered dither" technique can be used to display an M.times.M image with multiple levels of intensity on an M.times.M bilevel display. In the ordered dither technique, the decision to intensify or not intensify the pixel at position (X,Y) depends on the desired intensity I(X,Y) at that point and on an N.times.N dither matrix D.sup.N. The dither matrix D.sup.N is indexed from 0 to N-1 along its rows and columns. Each of the integers 0 to N.sup.2 -1 appears once in the matrix. For example, when N=2, D.sup.2 is given by ##EQU1## To process the pixel at (X,Y), the dither matrix index values i, j are computed as follows: EQU i=X modulo-N, j=Y modulo-N.
Then if I(X,Y) is greater than D.sub.ij.sup.N, the pixel at (X,Y) is intensified; otherwise it is not. The above techniques are discussed at pages 597-601 of Fundamentals of Interactive Computer Graphics, referenced above, and references cited therein.
Dithering thus has the effect of smoothing out the transition between two intensity levels. Circuitry for carrying out this dithering typically includes means for comparing the least significant part (e.g., the least significant nibble (LSN)) of the rendered intensity with a value stored in the dither cell at a row and column determined in accordance with the pixel sub-address (i.e., the fractional part of the pixel address). If the least significant part is greater than the dither cell value, then the most significant part (e.g., the MSN) of the rendered intensity is incremented. For example, consider a rendered image with eight-bit intensity values and a frame buffer having four bits per color. An exemplary dither cell is the 4.times.4 dither cell having the randomized values shown in FIG. 3. The LSNs of the rendered pixels define sixteen intensity levels with values from 0 to 15 which match the sixteen dither cell entries. The least significant two bits of both the X address and Y address of the pixel are used to select the cell value to be compared. The dither algorithm may be simply stated as follows: If I.sub.LSN is greater than D(X,Y), then I.sub.MSN =I.sub.MSN +1, where I.sub.LSN is the intensity value's least significant nibble, I.sub.MSN is the intensity value's most significant nibble and D(X,Y) is the dither cell value selected in accordance with the subaddresses of X and Y.
Exemplary circuitry for carrying out the dither algorithm is represented by the block diagram shown in FIG. 4. As shown, dither cell values D(X,Y) output from a dither matrix storage device 26 are input to a compare circuit 24. The dither cell values are compared with corresponding parts of input intensity values,, e.g., with the LSNs of corresponding input intensity values. If the LSN of an intensity value is greater than the dither cell value it is compared with, the MSN of that intensity value is incremented in adder 22 and combined with the LSN to form the output intensity value. In the prior art, most dither circuits use fixed or "hard wired" dither cell values. In addition, most prior art dither circuits have their row-column addresses fixed to corresponding (X,Y) screen addresses. These limitations create problems when the applications program employs windowing, since the pixel coordinates employed in most computations are window-relative as opposed to screen-relative. A further problem with known dither circuits is that their output intensities "wrap" to a low value when the input intensity is at a maximum.